package com.lry.basic.algorithm.stack;

import java.util.Stack;
//https://leetcode-cn.com/problems/maximum-subarray-min-product/
class CompleteStack {

    public static void main(String[] args) {
        System.out.println(maxSumMinProduct(new int[]{2,3,3,1,2}));
    }
    public static int maxSumMinProduct(int[] nums) {
        int n = nums.length;

        long[] sum = new long[n+1];
        for(int i=0;i<n;i++){
            sum[i+1] = sum[i] + nums[i];
        }


        int[] left = new int[n];//存储左边第一个小于当前值的下标
        Stack<Integer> stack = new Stack();
        for(int i=0;i<n;i++) {
            while(!stack.isEmpty()&&nums[stack.peek()] >= nums[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                left[i] = -1;
            }else{
                left[i] = stack.peek();
            }
            stack.push(i);
        }

        int[] right = new int[n];//存储右边第一个小于当前值的下标
        stack.clear();

        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty()&&nums[stack.peek()] >= nums[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = n;
            }else{
                right[i] = stack.peek();
            }
            stack.push(i);
        }


        long ans = 0;
        for(int i=0;i<n;i++){
            ans = Math.max(ans,nums[i]*(sum[right[i]]-sum[left[i]+1]));
        }
        return (int)(ans % 1000000007);
    }
}